import java.util.*;

/**
 * @author LKQ
 * @date 2022/3/26 10:42
 * @description 并查集
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[][] connections = {{0, 1}, {0, 2}, {0, 3}, {1, 2}, {1, 3}};
        solution.makeConnected(6, connections);
    }

    private int[] parent;

    public int makeConnected(int n, int[][] connections) {
        // n 个节点相互连通至少需要n-1条线
        if (connections.length < n - 1) {
            return -1;
        }
        // 初始化
        parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
        // 合并
        for (int[] connection : connections) {
            union(connection[0], connection[1]);
        }
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (parent[i] == i) {
                count++;
            }
        }
        return count - 1;
    }

    public void union(int node1, int node2) {
        int root1 = find(node1);
        int root2 = find(node2);
        if (root1 == root2) {
            return;
        }
        parent[root1] = root2;
    }

    public int find(int x) {
        return parent[x] == x ? x : (parent[x] = find(parent[x]));
    }
}
